{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Is Graph Bipartite?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isBipartite"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #判断二分图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "存在一个 <strong>无向图</strong> ，图中有 <code>n</code> 个节点。其中每个节点都有一个介于 <code>0</code> 到 <code>n - 1</code> 之间的唯一编号。给你一个二维数组 <code>graph</code> ，其中 <code>graph[u]</code> 是一个节点数组，由节点 <code>u</code> 的邻接节点组成。形式上，对于 <code>graph[u]</code> 中的每个 <code>v</code> ，都存在一条位于节点 <code>u</code> 和节点 <code>v</code> 之间的无向边。该无向图同时具有以下属性：\n",
    "<ul>\n",
    "\t<li>不存在自环（<code>graph[u]</code> 不包含 <code>u</code>）。</li>\n",
    "\t<li>不存在平行边（<code>graph[u]</code> 不包含重复值）。</li>\n",
    "\t<li>如果 <code>v</code> 在 <code>graph[u]</code> 内，那么 <code>u</code> 也应该在 <code>graph[v]</code> 内（该图是无向图）</li>\n",
    "\t<li>这个图可能不是连通图，也就是说两个节点 <code>u</code> 和 <code>v</code> 之间可能不存在一条连通彼此的路径。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>二分图</strong> 定义：如果能将一个图的节点集合分割成两个独立的子集 <code>A</code> 和 <code>B</code> ，并使图中的每一条边的两个节点一个来自 <code>A</code> 集合，一个来自 <code>B</code> 集合，就将这个图称为 <strong>二分图</strong> 。</p>\n",
    "\n",
    "<p>如果图是二分图，返回 <code>true</code><em> </em>；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/21/bi2.jpg\" style=\"width: 222px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,2,3],[0,2],[0,1,3],[0,2]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong><code>不能将节点分割成两个独立的子集，</code>以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/21/bi1.jpg\" style=\"width: 222px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>graph = [[1,3],[0,2],[1,3],[0,2]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong><code>可以将节点分成两组: {0, 2} 和 {1, 3} 。</code></pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>graph.length == n</code></li>\n",
    "\t<li><code>1 <= n <= 100</code></li>\n",
    "\t<li><code>0 <= graph[u].length < n</code></li>\n",
    "\t<li><code>0 <= graph[u][i] <= n - 1</code></li>\n",
    "\t<li><code>graph[u]</code> 不会包含 <code>u</code></li>\n",
    "\t<li><code>graph[u]</code> 的所有值 <strong>互不相同</strong></li>\n",
    "\t<li>如果 <code>graph[u]</code> 包含 <code>v</code>，那么 <code>graph[v]</code> 也会包含 <code>u</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [is-graph-bipartite](https://leetcode.cn/problems/is-graph-bipartite/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [is-graph-bipartite](https://leetcode.cn/problems/is-graph-bipartite/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[0,2],[0,1,3],[0,2]]', '[[1,3],[0,2],[1,3],[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import Deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        _type: List[int] = [None] * len(graph)\n",
    "        to_visit: Set[int] = set(n for n in range(len(graph)))\n",
    "        dq: Deque[int] = deque()\n",
    "\n",
    "        while len(to_visit) > 0:\n",
    "            dq.append(to_visit.pop())\n",
    "            while len(dq) > 0:\n",
    "                u: int = dq.popleft()\n",
    "                if _type[u] is None:\n",
    "                    _type[u] = 0\n",
    "                expected: int = 1 - _type[u]\n",
    "                for v in graph[u]:\n",
    "                    if _type[v] is None:\n",
    "                        _type[v] = expected\n",
    "                        dq.append(v)\n",
    "                        to_visit.remove(v)\n",
    "                    elif _type[v] != expected:\n",
    "                        return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def isBipartite(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        visited = [0] * len(graph)# 0-not visited; 1-blue; 2-red;\n",
    "        for i in range(len(graph)):\n",
    "            if graph[i] and visited[i] == 0:\n",
    "                visited[i] = 1\n",
    "                q = collections.deque()\n",
    "                q.append(i)\n",
    "                while q:\n",
    "                    v = q.popleft()#every point\n",
    "                    for e in graph[v]:#every edge\n",
    "                        if visited[e] != 0:\n",
    "                            if visited[e] == visited[v]:\n",
    "                                return False\n",
    "                        else:\n",
    "                            visited[e] = 3 - visited[v]\n",
    "                            q.append(e)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, graph, colors, color, num):\n",
    "        if colors[num] != -1:\n",
    "            return color == colors[num]\n",
    "        colors[num] = color\n",
    "        for t in graph[num]:\n",
    "            if not self.dfs(graph, colors, 1-color, t):\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def isBipartite(self, graph: 'List[List[int]]') -> 'bool':\n",
    "        size = len(graph)\n",
    "        colors = [-1]*size\n",
    "        for i in range(size):\n",
    "            if colors[i] == -1 and self.dfs(graph, colors, 0, i) == False:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # 着色问题，相连的节点不能有相同的颜色\n",
    "        # 这里的颜色数量是2\n",
    "        # 方法一：dfs\n",
    "        # time complexity: O(|V|+|E|), space complexity: O(|V|)\n",
    "        N = len(graph)\n",
    "        color = [0]*N # 0表示未被着色，1表示红色，-1表示黑色\n",
    "        def dfs(start, c):\n",
    "            if color[start] != 0:\n",
    "                return color[start] == c\n",
    "            color[start] = c\n",
    "            for neighbor in graph[start]:\n",
    "                if color[neighbor] != -c:\n",
    "                    if not dfs(neighbor, -c):\n",
    "                        return False\n",
    "            return True\n",
    "        for i in range(N):\n",
    "            if color[i] == 0: # 节点i还未被着色\n",
    "                if not dfs(i, 1):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def dfs(node, cur = 0):\n",
    "            save[cur].add(node)\n",
    "            for new in graph[node]:\n",
    "                if new in save[cur]:\n",
    "                    return False\n",
    "                if new not in save[1 - cur]:\n",
    "                    dfs(new, 1 - cur)\n",
    "            return True\n",
    "        \n",
    "        save = [set(), set()]\n",
    "        for i, row in enumerate(graph):\n",
    "            if i in save[0] or i not in save[1]:\n",
    "                if not dfs(i):\n",
    "                    return False\n",
    "            else:\n",
    "                if not dfs(i, 1):\n",
    "                    return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: bool\n",
    "        isBipartite() using BFS\n",
    "        1. using 2-colorable assign red color two the source\n",
    "        2. color all its neighbours with blue color\n",
    "        3. return colorble \n",
    "        \"\"\"\n",
    "        N = len(graph)\n",
    "        if N <= 2:\n",
    "            return True\n",
    "        else:\n",
    "            visited, red, blue = set([]), set([]), set([])\n",
    "            for i in range(N):\n",
    "                if graph[i] == []:\n",
    "                    visited.add(i)\n",
    "            if len(visited) >= N - 2:\n",
    "                return True\n",
    "            i = 0\n",
    "            while i in visited:\n",
    "                i += 1\n",
    "            red.add(i)\n",
    "            FLAG = \"R\"\n",
    "            while len(visited) < N:\n",
    "                lenV = len(visited)\n",
    "                if FLAG == \"R\":\n",
    "                    FLAG = \"B\"\n",
    "                    for rnode in red:\n",
    "                        if rnode not in visited:\n",
    "                            visited.add(rnode)\n",
    "                            for bnode in graph[rnode]:\n",
    "                                if bnode in red:\n",
    "                                    return False\n",
    "                                else:\n",
    "                                    blue.add(bnode)\n",
    "                        elif rnode in blue:\n",
    "                            return False\n",
    "                        \n",
    "                else:\n",
    "                    FLAG = \"R\"\n",
    "                    for bnode in blue:\n",
    "                        if bnode not in visited:\n",
    "                            visited.add(bnode)\n",
    "                            for rnode in graph[bnode]:\n",
    "                                if rnode in blue:\n",
    "                                    return False\n",
    "                                else:\n",
    "                                    red.add(rnode)\n",
    "                        elif bnode in red:\n",
    "                            return False\n",
    "                        \n",
    "                if lenV == len(visited):\n",
    "                    for i in range(N):\n",
    "                        if i not in visited:\n",
    "                            for node in graph[i]:\n",
    "                                red.add(node)\n",
    "                            FLAG = \"R\"\n",
    "                            break\n",
    "                            \n",
    "                            \n",
    "            return True\n",
    "                                \n",
    "                        \n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph):\n",
    "        \"\"\"\n",
    "        :type graph: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "\n",
    "        edges = collections.defaultdict(set)\n",
    "        for idx,points in enumerate(graph):\n",
    "            for p in points:\n",
    "                edges[idx].add(p)\n",
    "        colors = {}\n",
    "        def dfs(v,color):\n",
    "            ocolor = 1- color\n",
    "            for p in edges[v]:\n",
    "                if p not in colors:\n",
    "                    colors[p]=ocolor\n",
    "                    if not dfs(p,ocolor):\n",
    "                        return False\n",
    "                elif colors[p] != ocolor:\n",
    "                    return False\n",
    "            return True\n",
    "        for k in edges:\n",
    "            if k in colors:continue\n",
    "            else:\n",
    "                colors[k] = 0\n",
    "                if not dfs(k,0):\n",
    "                    return False\n",
    "        return True\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph):\n",
    "        nodes = [i for i in range(len(graph))]\n",
    "        r = [[], []]\n",
    "        while nodes:\n",
    "            node = nodes.pop(0)\n",
    "            r[0].append(node)\n",
    "            if self.dfs(node, nodes, graph, r, 0):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def dfs(self, node, nodes, graph, r, s):\n",
    "        for i in graph[node]:\n",
    "            if i in r[s]:\n",
    "                return True\n",
    "            if i in nodes:\n",
    "                nodes.remove(i)    \n",
    "                r[1-s].append(i)\n",
    "                if self.dfs(i, nodes, graph, r, 1-s):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        #DFS + 染色法:0为蓝色，1位红色\n",
    "        color = {}\n",
    "        for node in range(len(graph)):\n",
    "            if node not in color:   #如果node还没有被着色\n",
    "                stack = [node]  #在栈中加入这个node\n",
    "                color[node] = 0     #将这个node着色为蓝色\n",
    "                while stack:    #to-do list\n",
    "                    node = stack.pop()  #这是我下一个需要处理的点,实质是处理这个点的neighbor\n",
    "                    for nei in graph[node]:\n",
    "                        if nei not in color:\n",
    "                            stack.append(nei)\n",
    "                            color[nei] = color[node] ^ 1    #将这个nei取相反的颜色\n",
    "                        elif color[nei] == color[node]:\n",
    "                            return False    #如果存在nei于node颜色相同则返回False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        if len(graph) <= 2:\n",
    "            return True\n",
    "        groups = [-1] * len(graph)\n",
    "        for i in range(len(graph)):\n",
    "            if groups[i] != -1:\n",
    "                continue\n",
    "            group = 0\n",
    "            groups[i] = group\n",
    "            layer = [i]\n",
    "            next_layer = []\n",
    "            while layer:\n",
    "                point = layer.pop(0)\n",
    "                for p in graph[point]:\n",
    "                    if groups[p] != -1 and groups[p] == group:\n",
    "                        return False\n",
    "                    if groups[p] == -1:\n",
    "                        groups[p] = (group + 1) %2\n",
    "                        next_layer.append(p)\n",
    "                if not layer:\n",
    "                    group = (group + 1)%2\n",
    "                    layer = next_layer\n",
    "                    next_layer = []\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "#         color = {}\n",
    "#         for node in range(len(graph)):\n",
    "#             if node not in color:\n",
    "#                 color[node] = 0\n",
    "#             for i in graph[node]:\n",
    "#                 if i not in color:\n",
    "#                     color[i] = color[node] ^ 1\n",
    "#                 elif color[i] == color[node]:\n",
    "#                     return False\n",
    "#         return True\n",
    "class Solution(object):\n",
    "    def isBipartite(self, graph):\n",
    "        color = {}\n",
    "        for node in range(len(graph)):\n",
    "            if node not in color:\n",
    "                stack = [node]\n",
    "                color[node] = 0\n",
    "                while stack:\n",
    "                    node = stack.pop()\n",
    "                    for nei in graph[node]:\n",
    "                        if nei not in color:\n",
    "                            stack.append(nei)\n",
    "                            color[nei] = color[node] ^ 1\n",
    "                        elif color[nei] == color[node]:\n",
    "                            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        #思路 就是一个一个节点的去判断\n",
    "        color = {}\n",
    "        for node in range(len(graph)):\n",
    "            quenue = []\n",
    "            quenue.append(node)\n",
    "            while quenue:\n",
    "                pop_node = quenue.pop(0)\n",
    "                if pop_node not in color:\n",
    "                    color[pop_node] = 1\n",
    "                for next_node in graph[pop_node]: #取到[1,3]里面的值\n",
    "                    if next_node not in color: #\n",
    "                        color[next_node] = color[pop_node]^1 #在上面的节点上取反 就行\n",
    "                        quenue.append(next_node)\n",
    "                    else:\n",
    "                        if color[next_node] == color[pop_node]:\n",
    "                            return False\n",
    "        return True\n",
    "\n",
    "                    \n",
    "        # #思路 就是一个一个节点的去判断\n",
    "        # color = {}\n",
    "        # for node in range(len(graph)):\n",
    "        #     if graph[node] not in color:\n",
    "        #         color[node] = 1\n",
    "        #     for next_node in graph[node]: #取到[1,3]里面的值\n",
    "        #         if graph[next_node] not in color: #\n",
    "        #             color[next_node] = color[node]^1 #在上面的节点上取反 就行\n",
    "        #         else:\n",
    "        #             return False\n",
    "        # #上面的没有循环去找下一层的情况 所以用BFS\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        V = len(graph)\n",
    "        R, C = len(graph), len(graph[0])\n",
    "        W,G,B,MASK = 0,1,2,3\n",
    "        st = defaultdict(int)\n",
    "        \n",
    "        def bfs(node,color):\n",
    "            Q = deque([(node,color)])\n",
    "            st[node] = color\n",
    "            while Q:\n",
    "                n,c = Q.popleft()\n",
    "                for nei in graph[n]:\n",
    "                    if st[nei] ==W:\n",
    "                        st[nei] = c^MASK\n",
    "                        Q.append((nei,c^MASK))\n",
    "                    elif st[nei] == c:    \n",
    "                        return False\n",
    "            return True        \n",
    "                        \n",
    "                        \n",
    "        for node in range(V):\n",
    "            if st[node] == W:\n",
    "                if not bfs(node, G):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        dq = deque()\n",
    "        color = {}\n",
    "        for i in range(len(graph)):\n",
    "            if i not in color:\n",
    "                dq.append(i)\n",
    "                color[i] = True\n",
    "                while dq:\n",
    "                    node = dq.popleft()\n",
    "                    for neighbor in graph[node]:\n",
    "                        if neighbor not in color:\n",
    "                            dq.append(neighbor)\n",
    "                            color[neighbor] = not color[node]\n",
    "                        elif color[neighbor] == color[node]:\n",
    "                            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        color = [UNCOLORED] * n\n",
    "        valid = True\n",
    "\n",
    "        def dfs(node: int, c: int):\n",
    "            nonlocal valid\n",
    "            color[node] = c\n",
    "            cNei = (GREEN if c == RED else RED)\n",
    "            for neighbor in graph[node]:\n",
    "                if color[neighbor] == UNCOLORED:\n",
    "                    dfs(neighbor, cNei)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif color[neighbor] != cNei:\n",
    "                    valid = False\n",
    "                    return\n",
    "\n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                dfs(i, RED)\n",
    "                if not valid:\n",
    "                    break\n",
    "        \n",
    "        return valid\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        def dfs(lst, from_set, to_set):\n",
    "            for i in lst:\n",
    "                if i in from_set:\n",
    "                    return False\n",
    "                if i not in to_set:\n",
    "                    to_set.add(i)\n",
    "                    if not dfs(graph[i], to_set, from_set):\n",
    "                        return False\n",
    "            return True\n",
    "            \n",
    "        l, r = set(), set()\n",
    "        for i, lst in enumerate(graph):\n",
    "            if i in l or i in r:\n",
    "                continue\n",
    "            l.add(i)\n",
    "            if not dfs(lst, l, r):\n",
    "                return False\n",
    "        print(l, r)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        colors = [None] * len(graph)\n",
    "        def paint(i, color):\n",
    "            if colors[i] == color:\n",
    "                return True\n",
    "            if colors[i] is not None:\n",
    "                return False\n",
    "            colors[i] = color\n",
    "            return all(\n",
    "                paint(neighbor, color ^ 1)\n",
    "                for neighbor in graph[i]\n",
    "            )\n",
    "        for i in range(len(graph)):\n",
    "            if colors[i] is not None:\n",
    "                continue\n",
    "            if not paint(i, 0):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\r\n",
    "        return self.isBipartiteDfs(graph)\r\n",
    "\r\n",
    "    def isBipartiteDfs(self, graph: List[List[int]]) -> bool:\r\n",
    "        marked = set()\r\n",
    "        a = set()\r\n",
    "        b = set()\r\n",
    "        def dfs(graph:List[List[int]], start:int) -> bool:\r\n",
    "            print(\"dfs\", start)\r\n",
    "            # visit\r\n",
    "            if start not in marked:\r\n",
    "                # print(start)\r\n",
    "                marked.add(start)\r\n",
    "                if start not in a and start not in b:\r\n",
    "                    a.add(start)\r\n",
    "            \r\n",
    "            adj = b if start in a else a\r\n",
    "            sel = a if start in a else b\r\n",
    "            \r\n",
    "            result = True\r\n",
    "            for c in graph[start]:\r\n",
    "                print(start, c)\r\n",
    "                \r\n",
    "                if c not in marked:                    \r\n",
    "                    if c not in sel:\r\n",
    "                        adj.add(c)\r\n",
    "                    result = dfs(graph, c) and result\r\n",
    "                else:\r\n",
    "                    print(c, \"已处理\")\r\n",
    "\r\n",
    "                if c in sel:\r\n",
    "                    print(\"失败冲突\")\r\n",
    "                    return False\r\n",
    "\r\n",
    "            return result\r\n",
    "\r\n",
    "        for i in range(len(graph)):\r\n",
    "            if not dfs(graph, i):\r\n",
    "                return False\r\n",
    "        \r\n",
    "        print(a, b)\r\n",
    "\r\n",
    "        return True\r\n",
    "\r\n",
    "    def isBipartiteBfs(self, graph: List[List[int]]) -> bool:\r\n",
    "        queue = []\r\n",
    "        marked = set()\r\n",
    "        a = set()\r\n",
    "        b = set()\r\n",
    "\r\n",
    "        for i in range(len(graph)):\r\n",
    "            if i not in marked:\r\n",
    "                queue.append(i)\r\n",
    "            \r\n",
    "            while queue:\r\n",
    "                cur = queue.pop(0)\r\n",
    "                if cur not in marked:\r\n",
    "                    # print(cur)\r\n",
    "                    # 遍历到的节点，加入到集合中\r\n",
    "                    marked.add(cur)\r\n",
    "                    if cur not in a and cur not in b:\r\n",
    "                        a.add(cur)\r\n",
    "                \r\n",
    "                adj = b if cur in a else a\r\n",
    "                sel = a if cur in a else b\r\n",
    "\r\n",
    "                # 相邻的节点，如果是在cur相同的集合中，就冲突了，返回失败\r\n",
    "                # 否则的话，加入不同的那个集合\r\n",
    "                # 同时加入队列，进行下一层的迭代\r\n",
    "\r\n",
    "                for c in graph[cur]:\r\n",
    "                    if c not in marked:\r\n",
    "                        queue.append(c)\r\n",
    "                        if c in sel:\r\n",
    "                            return False\r\n",
    "                        else:\r\n",
    "                            adj.add(c)\r\n",
    "\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        lst = [None]*n\n",
    "        st = set()\n",
    "\n",
    "        dct = {}\n",
    "        for inx, i in enumerate(graph):\n",
    "            dct[inx] = i\n",
    "\n",
    "        def dfs(cur: int, up: bool, run: bool) -> bool:\n",
    "            if run and lst[cur] != None:\n",
    "                return True\n",
    "            if cur in st:\n",
    "                if up == True:\n",
    "                    if lst[cur] == True:\n",
    "                        return False\n",
    "                if up == False:\n",
    "                    if lst[cur] == False:\n",
    "                        return False\n",
    "                    return True\n",
    "            st.add(cur)\n",
    "            if up == True:\n",
    "                if lst[cur] == True:\n",
    "                    return False\n",
    "            if up == False:\n",
    "                if lst[cur] == False:\n",
    "                    return False\n",
    "            lst[cur] = not up\n",
    "            return all([dfs(i, not up, False) for i in dct[cur]])\n",
    "\n",
    "        for i in range(n):\n",
    "            st = set()\n",
    "            if not dfs(i, True, True):\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        color = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            if color[i] == 0:\n",
    "                q = collections.deque([i])\n",
    "                color[i] = 1\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    # cNei = (GREEN if color[node] == RED else RED)\n",
    "                    for neighbor in graph[node]:\n",
    "                        if color[neighbor] == 0:\n",
    "                            q.append(neighbor)\n",
    "                            color[neighbor] = -color[node]\n",
    "                        elif color[neighbor] != -color[node]:\n",
    "                            return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        color = [UNCOLORED] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                q = collections.deque([i])\n",
    "                color[i] = RED\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    cNei = (GREEN if color[node] == RED else RED)\n",
    "                    for neighbor in graph[node]:\n",
    "                        if color[neighbor] == UNCOLORED:\n",
    "                            q.append(neighbor)\n",
    "                            color[neighbor] = cNei\n",
    "                        elif color[neighbor] != cNei:\n",
    "                            return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        visited = [0 for _ in range(len(graph))]\n",
    "\n",
    "        def dfs(node: int) -> bool:\n",
    "            if visited[i] != 0:\n",
    "                return True\n",
    "            visited[i] = 1\n",
    "\n",
    "            queue = deque()\n",
    "            queue.append(node)\n",
    "\n",
    "            while queue:\n",
    "                cur = queue.popleft()\n",
    "                cur_color = visited[cur]\n",
    "                for neighbor in graph[cur]:\n",
    "                    if visited[neighbor] == cur_color:\n",
    "                        return False\n",
    "                    elif visited[neighbor] == -cur_color:\n",
    "                        continue\n",
    "                    else:\n",
    "                        visited[neighbor] = -cur_color\n",
    "                        queue.append(neighbor)\n",
    "\n",
    "            return True\n",
    "\n",
    "        for i in range(len(graph)):\n",
    "            if not dfs(i):\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        self.ok = True\n",
    "        n = len(graph)\n",
    "        self.color = [False] * n \n",
    "        self.visited = [False] * n \n",
    "        for v in range(n):\n",
    "            if not self.visited[v]:\n",
    "                self.traverse(graph,v)\n",
    "        return self.ok \n",
    "\n",
    "\n",
    "    def traverse(self, graph, v):\n",
    "        if not self.ok:\n",
    "            return \n",
    "        self.visited[v] = True\n",
    "        for w in graph[v]:\n",
    "            if not self.visited[w]:\n",
    "                self.color[w] = not self.color[v]\n",
    "                self.traverse(graph, w)\n",
    "            else:\n",
    "                if self.color[w] ==self.color[v]:\n",
    "                    self.ok = False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        uncolored, red, green = 0, 1, 2\n",
    "        nodes = [uncolored] * n  \n",
    "        valid = True\n",
    "\n",
    "        def dfs(i, color):\n",
    "            nonlocal valid\n",
    "            nodes[i] = color \n",
    "            next_color = (green if color == red else red)\n",
    "            for ni in graph[i]:\n",
    "                if nodes[ni] == uncolored:\n",
    "                    dfs(ni, next_color)\n",
    "                    if not valid:\n",
    "                        return \n",
    "                elif nodes[ni] != next_color:\n",
    "                    valid = False\n",
    "                    return \n",
    "        for i in range(n):\n",
    "            if nodes[i] == uncolored:\n",
    "                dfs(i, red) \n",
    "            if not valid:\n",
    "                break\n",
    "        return valid \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        color = [UNCOLORED] * n\n",
    "        valid = True\n",
    "\n",
    "        def dfs(node: int, c: int):\n",
    "            nonlocal valid\n",
    "            color[node] = c\n",
    "            cNei = (GREEN if c == RED else RED)\n",
    "            for neighbor in graph[node]:\n",
    "                if color[neighbor] == UNCOLORED:\n",
    "                    dfs(neighbor, cNei)\n",
    "                    if not valid:\n",
    "                        return\n",
    "                elif color[neighbor] != cNei:\n",
    "                    valid = False\n",
    "                    return\n",
    "\n",
    "        for i in range(n):\n",
    "            if color[i] == UNCOLORED:\n",
    "                dfs(i, RED)\n",
    "                if not valid:\n",
    "                    break\n",
    "        \n",
    "        return valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\r\n",
    "        n = len(graph)\r\n",
    "        self.is_ok = True\r\n",
    "        self.color = [False] * n\r\n",
    "        self.visited =  [False] * n\r\n",
    "        for s in range(n):\r\n",
    "            if not self.visited[s]:\r\n",
    "                self.bfs(graph, s)\r\n",
    "            # if not self.is_ok:\r\n",
    "            #     break\r\n",
    "        return self.is_ok\r\n",
    "\r\n",
    "    def bfs(self, graph, s):\r\n",
    "        q = deque()\r\n",
    "        q.append(s)\r\n",
    "        self.visited[s] = True\r\n",
    "        while q and self.is_ok:\r\n",
    "            cur = q.popleft()\r\n",
    "            for v in graph[cur]:\r\n",
    "                if not self.visited[v]:\r\n",
    "                    self.color[v] = not self.color[cur]\r\n",
    "                    self.visited[v] = True\r\n",
    "                    q.append(v)\r\n",
    "                else:\r\n",
    "                    if self.color[v] == self.color[cur]:\r\n",
    "                        self.is_ok = False\r\n",
    "                        return\r\n",
    "\r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionSet:\n",
    "    def __init__(self, n):\n",
    "        self.rank = [1] * n\n",
    "        self.parent = [i for i in range(n)]\n",
    "       \n",
    "    \n",
    "    def find(self, x):\n",
    "        if x != self.parent[x]:\n",
    "           self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        if rootx != rooty:\n",
    "            if self.rank[rootx] > self.rank[rooty]:\n",
    "                self.parent[rooty] = rootx\n",
    "            else:\n",
    "                self.parent[rootx] = rooty\n",
    "            if self.rank[rootx] == self.rank[rooty]:\n",
    "                self.rank[rooty] +=1 \n",
    "        \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        unionSet = UnionSet(n)\n",
    "        for i in range(n):\n",
    "            gra = graph[i]\n",
    "            for j in range(1, len(gra)):\n",
    "                unionSet.union(gra[0],gra[j])\n",
    "            if len(gra) and unionSet.find(i) == unionSet.find(gra[0]):\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        # bfs\n",
    "        n = len(graph)\n",
    "        uncolor, red, green = 0, 1, 2\n",
    "        color = [uncolor] * n\n",
    "        for i in range(n):\n",
    "            if color[i] == uncolor:\n",
    "                q = deque([i])\n",
    "                color[i] = red\n",
    "                while q:\n",
    "                    node = q.popleft()\n",
    "                    cNei = green if color[node] == red else red\n",
    "                    for neighbor in graph[node]:\n",
    "                        if color[neighbor] == uncolor:\n",
    "                            q.append(neighbor)\n",
    "                            color[neighbor] = cNei\n",
    "                        elif color[neighbor] != cNei:\n",
    "                            return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "        # # dfs\n",
    "        # n = len(graph)\n",
    "        # UNCOLORED, RED, GREEN = 0, 1, 2\n",
    "        # color = [UNCOLORED] * n\n",
    "        # valid = True\n",
    "        # def dfs(node: int, c: int):\n",
    "        #     nonlocal valid\n",
    "        #     color[node] = c\n",
    "        #     cNei = (GREEN if c == RED else RED)\n",
    "        #     for neighbor in graph[node]:\n",
    "        #         if color[neighbor] == UNCOLORED:\n",
    "        #             dfs(neighbor, cNei)\n",
    "        #             if not valid:\n",
    "        #                 return\n",
    "        #         elif color[neighbor] != cNei:\n",
    "        #             valid = False\n",
    "        #             return\n",
    "        # for i in range(n):\n",
    "        #     if color[i] == UNCOLORED:\n",
    "        #         dfs(i, RED)\n",
    "        #         if not valid:\n",
    "        #             break\n",
    "        # return valid\n",
    "\n",
    "\n",
    "\n",
    "        # n = len(graph)\n",
    "        # vis = [False]*n\n",
    "        # color = [False]*n\n",
    "        # isBi = True\n",
    "        # def tranverse(g,v):\n",
    "        #     nonlocal vis,color,isBi\n",
    "        #     if not isBi:\n",
    "        #         return\n",
    "        #     vis[v] = True\n",
    "        #     for d in g[v]:\n",
    "        #         if not vis[d]:\n",
    "        #             color[d] = not color[v]\n",
    "        #             tranverse(g,d)\n",
    "        #         else:\n",
    "        #             if color[d] ==color[v]:\n",
    "        #                 isBi = False\n",
    "        # for i in range(len(graph)):\n",
    "        #     if not vis[i]:\n",
    "        #         tranverse(graph,i)\n",
    "        # return isBi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = [i for i in range(n)]\n",
    "    \n",
    "    def find(self, n: int) -> int:\n",
    "        while n != self.parent[n]:\n",
    "            cur = self.parent[n]\n",
    "            self.parent[n] = self.parent[self.parent[n]]\n",
    "            n = cur\n",
    "        return n\n",
    "    \n",
    "    def union(self, i: int, j: int):\n",
    "        pi = self.find(i)\n",
    "        pj = self.find(j)\n",
    "        if pi == pj:\n",
    "            return\n",
    "        self.parent[pi] = pj\n",
    "    \n",
    "    def connected(self, i: int, j: int) -> bool:\n",
    "        return self.find(i) == self.find(j)\n",
    "        \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isBipartite(self, graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        v1 = set()\n",
    "        v2 = set()\n",
    "        visited = set()\n",
    "        def color(i):\n",
    "            if i in visited:\n",
    "                return\n",
    "            visited.add(i)\n",
    "            for v in graph[i]:\n",
    "                if i in v1 and v in v1:\n",
    "                    return False\n",
    "                if i in v2 and v in v2:\n",
    "                    return False\n",
    "                if v in v1 or v in v2:\n",
    "                    continue\n",
    "                (v2 if i in v1 else v1).add(v)\n",
    "            for v in graph[i]:\n",
    "                if color(v) == False:\n",
    "                    return False\n",
    "\n",
    "        for i in range(n):\n",
    "            if i not in v1 and i not in v2:\n",
    "                v1.add(i)\n",
    "                if color(i) == False:\n",
    "                    return False\n",
    "        return True\n",
    "\n",
    "                   "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
